import java.util.*;

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 */
public class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        int zeroNum = 0;
        List<Integer> negativeList = new ArrayList<>();
        List<Integer> positiveList = new ArrayList<>();
        Set<Integer> unique = new HashSet<>();
        Set<Integer> twoValue = new HashSet<>();

        for (int n : nums) {
            if (0 == n) {
                zeroNum++;
                continue;
            }
            if (unique.contains(n)) {
                twoValue.add(n);
            } else {
                unique.add(n);
                if (n < 0) {
                    negativeList.add(n);
                } else {
                    positiveList.add(n);
                }
            }
        }

        if (zeroNum > 2) {
            result.add(Arrays.asList(0, 0, 0));
        }
        if (zeroNum > 0) {
            for (int n : negativeList) {
                if (unique.contains(-n)) {
                    result.add(Arrays.asList(n, 0, -n));
                }
            }
        }

        for (int s : twoValue) {
            if (unique.contains(-(2 * s))) {
                result.add(Arrays.asList(s, s, -(2 * s)));
            }
        }

        int leftValue;
        int rightValue;
        int temp;

        for (int l = 0; l < negativeList.size(); l++) {
            leftValue = negativeList.get(l);
            for (int r = l+1; r < negativeList.size(); r++) {
                rightValue = negativeList.get(r);
                temp = -(leftValue + rightValue);
                if (unique.contains(temp)) {
                    result.add(Arrays.asList(leftValue, rightValue, temp));
                }
            }
        }

        for (int l = 0; l < positiveList.size(); l++) {
            leftValue = positiveList.get(l);
            for (int r = l+1; r < positiveList.size(); r++) {
                rightValue = positiveList.get(r);
                temp = -(leftValue + rightValue);
                if (unique.contains(temp)) {
                    result.add(Arrays.asList(leftValue, rightValue, temp));
                }
            }
        }

        return result;
    }

}